﻿using System;

namespace JoshuaOneEight.Services
{
	public class Diff
	{
		#region Constructors

		public Diff( string string1, string string2 )
		{
			mString1 = string1;
			mString2 = string2;
		}

		#endregion Constructors

		#region Diff Members

		public Result[] GetResults()
		{
			if( mResults == null )
			{
				mResults = new Result[mString1.Length];

				for( int i = 0; i < mString1.Length; i++ )
				{
					Result result = new Result();
					result.Letter = mString1[i];
					result.Matches = false;
					mResults[i] = result;
				}

				_ReadLCSFromBacktrack( _LongestCommonSubsequence( mString1, mString2 ),
					mString1, mString2, mString1.Length - 1, mString2.Length - 1 );
			}

			return mResults;
		}

		#endregion Diff Members

		#region Private Members

		private Result[] mResults;
		private readonly string mString1;
		private readonly string mString2;

		private int[,] _LongestCommonSubsequence( string s1, string s2 )
		{
			//if either string is empty, the length must be 0
			if( string.IsNullOrEmpty( s1 ) || string.IsNullOrEmpty( s2 ) )
				return null;

			int[,] num = new int[s1.Length, s2.Length];  //2D array
			char letter1;
			char letter2;

			//Actual algorithm
			for( int i = 0; i < s1.Length; i++ )
			{
				for( int j = 0; j < s2.Length; j++ )
				{
					letter1 = s1[i];
					letter2 = s2[j];

					if( letter1 == letter2 )
					{
						if( (i == 0) || (j == 0) )
							num[i, j] = 1;
						else
							num[i, j] = 1 + num[i - 1, j - 1];
					}
					else
					{
						if( (i == 0) && (j == 0) )
							num[i, j] = 0;
						else if( (i == 0) && !(j == 0) )   //First ith element
							num[i, j] = Math.Max( 0, num[i, j - 1] );
						else if( !(i == 0) && (j == 0) )   //First jth element
							num[i, j] = Math.Max( num[i - 1, j], 0 );
						else if( !(i == 0) && !(j == 0) )
							num[i, j] = Math.Max( num[i - 1, j], num[i, j - 1] );
					}
				}
			}

			return num;
		}

		private void _ReadLCSFromBacktrack( int[,] backtrack, string string1, string string2, int s1position, int s2posision )
		{
			if( s1position >= 0 && s2posision >= 0 && 
				string1[s1position] == string2[s2posision] )
			{
				Result result = mResults[s1position];
				result.Matches = true;
				mResults[s1position] = result;

				_ReadLCSFromBacktrack( backtrack, string1, string2, s1position - 1, s2posision - 1 );
			}
			else if( s1position > 0 )
			{
				if( s2posision > 0 && backtrack[s1position, s2posision - 1] >= backtrack[s1position - 1, s2posision] )
				{
					_ReadLCSFromBacktrack( backtrack, string1, string2, s1position, s2posision - 1 );
				}
				else
				{
					_ReadLCSFromBacktrack( backtrack, string1, string2, s1position - 1, s2posision );
				}
			}
		}

		#endregion Private Members

		#region Other

		public struct Result
		{
			#region Result Members

			public bool Matches;
			public char Letter;

			#endregion Result Members

		}

		#endregion Other

	}
}